package algorithme;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Graphe {

	private ArrayList<Arete> aretes;

	private Map<Integer, Set<Arete>> aretesAdjacentes = new HashMap<Integer, Set<Arete>>();

	private Map<Integer, Set<Arete>> aretesAdjacentes2 = new HashMap<Integer, Set<Arete>>();

	private UnionFind unionFind;

	public Graphe() {
		unionFind = new UnionFind(0);
		aretes = new ArrayList<Arete>();
	}

	public Graphe(Graphe g) {
		unionFind = new UnionFind(g.unionFind);
		aretes = new ArrayList<Arete>(g.aretes);
		
		aretesAdjacentes = new HashMap<Integer, Set<Arete>>();
		for (Map.Entry<Integer, Set<Arete>> e : g.aretesAdjacentes.entrySet())
			aretesAdjacentes.put(e.getKey(), new HashSet<Arete>(e.getValue()));
		
		aretesAdjacentes2 = new HashMap<Integer, Set<Arete>>();
		for (Map.Entry<Integer, Set<Arete>> e : g.aretesAdjacentes2.entrySet())
			aretesAdjacentes2.put(e.getKey(), new HashSet<Arete>(e.getValue()));
	}

	public Graphe(Collection<Arete> aretes) {
		this.aretes = new ArrayList<Arete>(aretes.size());
		for (Arete arete : aretes)
			ajouterArete(arete);
		unionFind = new UnionFind(nbSommets());
	}

	private void ajouterAretePrivate(Arete arete) {
		aretes.add(arete);
		lierSommetsAretes(arete);
	}

	public void ajouterArete(Arete arete) {
		ajouterAretePrivate(arete);
		unionFind = new UnionFind(nbSommets());
	}

	public void ajouterAretes(Collection<Arete> aretes) {
		for (Arete arete : aretes)
			ajouterAretePrivate(arete);
		unionFind = new UnionFind(nbSommets());
	}

	private void lierSommetsAretes(Arete arete) {
		lierSommetArete(arete.getU(), arete);
		lierSommetArete(arete.getV(), arete);
	}

	private void lierSommetArete(int sommet, Arete arete) {
		getAretesAdjacentes(sommet).add(arete);
		getAretesAdjacentes2(sommet).add(arete);
	}

	public int nbSommets() {
		return aretesAdjacentes.keySet().size();
	}

	public Set<Integer> getSommets() {
		return aretesAdjacentes.keySet();
	}

	public List<Arete> getAretes() {
		return aretes;
	}

	public int nbAretes() {
		return aretes.size();
	}

	public Set<Arete> getAretesAdjacentes(int sommet) {
		if (!aretesAdjacentes.containsKey(sommet))
			aretesAdjacentes.put(sommet, new HashSet<Arete>());
		return aretesAdjacentes.get(sommet);
	}

	public Set<Arete> getAretesAdjacentes2(int sommet) {
		if (!aretesAdjacentes2.containsKey(sommet))
			aretesAdjacentes2.put(sommet, new HashSet<Arete>());
		return aretesAdjacentes2.get(sommet);
	}

	public Map<Integer, Set<Arete>> getAretesAdjacentes2() {
		return aretesAdjacentes2;
	}
	
	public void supprimerArete(Arete arete){
		aretes.remove(arete);
		aretesAdjacentes.get(unionFind.find(arete.getU())).remove(arete);
		aretesAdjacentes.get(unionFind.find(arete.getV())).remove(arete);
		aretesAdjacentes2.get(arete.getU()).remove(arete);
		aretesAdjacentes2.get(arete.getV()).remove(arete);
	}

	public void unir(Arete arete) {
		int u = unionFind.find(arete.getU());
		int v = unionFind.find(arete.getV());
		unionFind.union(arete.getU(), arete.getV());
		int pere = unionFind.find(u);
		getAretesAdjacentes(pere).remove(arete);
		if (pere != u) {
			unirAretes(pere, u);
			aretesAdjacentes.remove(u);
		}
		if (pere != v) {
			unirAretes(pere, v);
			aretesAdjacentes.remove(v);
		}
	}

	private void unirAretes(int pere, int fils) {
		Collection<Arete> aretes_pere = getAretesAdjacentes(pere);
		aretes_pere.addAll(getAretesAdjacentes(fils));
		for (Arete a : getAretesAdjacentes(fils)) {
			if (unionFind.find(a.getU()) == unionFind.find(a.getV()))
				aretes_pere.remove(a);
		}
	}
	
	public String toString() {
		return aretes.toString();
	}

}
